1. Field of the Invention
The present invention relates to a method, system, and program for generating threshold values in a dither matrix.
2. Description of the Related Art
Most printers today can print in only a limited number of colors. Digital halftoning is a technique for printing a picture (or more generally displaying it on some two-dimensional medium) using small dots of a limited number of colors such that it appears to consist of many colors or shades of grey when viewed from a proper distance. For example, a picture of black and white dots can appear to display grey levels when viewed from some distance.
A popular method for digital halftoning is accomplished using a dithering algorithm which generates a dither mask or array having threshold values. The pixel values in the image comprise one of many greyscale or color values. Each pixel value is compared to a corresponding threshold value in the dither mask to determine whether the halftone output for that pixel is “on” (i.e. a dot will be printed at that pixel, and this can be represented numerically as the halftone pixel having a value 1) or “off” (i.e. a dot will not be printed at that pixel, represented numerically as the halftone pixel with value 0). Dither arrays use periodic patterns of threshold values which can have an unpleasant rendering at certain gray levels.
Too much randomness in the design of a dither array blurs the image and yields unaesthetic results. Techniques have been developed to increase the effect of blue noise with low frequencies attenuated to improve the visual effect of the image, such as that described in U.S. Pat. Ser. No. 5,726,772. In halftoning, blue noise is the statistical model describing the ideal spatial and spectral characteristics of aperiodic dispersed-dot dither patterns to attempt to produce stochastic dither patterns of the same-sized dots distributed as homogeneously as possible. Stochastic or blue noise patterns have also been used to improve clustered periodic dither mask as described in U.S. Pat. Ser. No. 6,025,930.
A step in typical methods to generate a dither mask that increases the desirable effect of blue noise is the filtering operation, where the values in the dither mask or a halftone pattern obtained from a dither mask may be filtered, such that each pixel value in the array is calculated as a weighed average of values that surround the subject pixel value, as described in C. W. Wu, G. Thompson, M. Stanich, “A unified framework for digital halftoning and dither mask construction: variations on a theme and implementation issues (Focal Paper),” NIP 19: IS&T's International Conference on Digital Printing Technologies, New Orleans, La., 2003, pp. 793-796. As described in this paper, many algorithms for generating dither masks have this filtering operation in common. The rest of the algorithm can be different depending on the algorithm and the application. Since the image to be halftoned is generally much larger than the dither mask, FIG. 1 illustrates how, in the prior art, repeated instances of a dithering mask 2a, 2b, 2c, 2d are arranged in a tile pattern superimposed over an image to provide threshold values for the pixel values in the image to determine the output for the pixel values in the image. A filter region 4 is used to determine surrounding threshold values to a center pixel value, e.g., “88” in mask 2a that falls within the filter region 4, such that a weighted average of the surrounding values of “88” as defined in the filter region 4 are calculated to produce filtered threshold values for a filtered dither mask. If the filter region 4 extends beyond the mask 2a including the threshold pixel whose filtered value being calculated, then the threshold value outside of the region of the matrix wraps around to the other side of the matrix. For instance, the surrounding value in the filter region 4 below the cell having value “97” wraps around to the other side to provide the threshold value “17”, which I shown in the instance of the dither mask 2c. These surrounding values in the portion of the filter region 4 that extend beyond the mask 2a are referred to as “wrap around values”.
In prior art methods for generating stochastic or blue noise masks, the dither mask is tiled as shown in FIG. 1, i.e. the dither masks are arranged with the edges aligned with each other. This condition is especially necessary in implementations where a Fourier transform based method is used to perform the filtering or convolution operation. In this case, the wrap around corresponds to circular convolution which can be easily implemented in a computer algorithm using the Fast Fourier Transform.
There is a need in the art for improved techniques for generating and filtering dither masks to improve the visual effects of a printed or displayed image.